Question #1: Outliers

Loading up the data

require(outliers)
Loading required package: outliers
url <- "https://d37djvu3ytnwxt.cloudfront.net/assets/courseware/v1/17b85cea5d0e613bf08025ca2907b62f/asset-v1:GTx+ISYE6501x+3T2017+type@asset+block/uscrime.txt"
df <- read.table(url, header = TRUE)
dim(df)
[1] 47 16
# Seperating the last column we will examine into a variable
crime_per_capita <- df[,'Crime']
length(crime_per_capita)
[1] 47
crime_per_capita
 [1]  791 1635  578 1969 1234  682  963 1555  856  705 1674  849  511  664  798  946  539  929
[19]  750 1225  742  439 1216  968  523 1993  342 1216 1043  696  373  754 1072  923  653 1272
[37]  831  566  826 1151  880  542  823 1030  455  508  849

Perfroming Grubbs test for outliers

To determine whether the highest and lowest values are potential outliers, I used the grubbs.test() function with type=10 which looks for one outlier. The first test looks at the highest value in the set and the second looks for the lowest value, indicated by using opposite=True.

# Testing for the highest value
grubbs.test(crime_per_capita, type=10, opposite = FALSE)

    Grubbs test for one outlier

data:  crime_per_capita
G = 2.81290, U = 0.82426, p-value = 0.07887
alternative hypothesis: highest value 1993 is an outlier
# Testing for the highest value
grubbs.test(crime_per_capita, type=10, opposite = TRUE)

    Grubbs test for one outlier

data:  crime_per_capita
G = 1.45590, U = 0.95292, p-value = 1
alternative hypothesis: lowest value 342 is an outlier

The returned results seem a bit curious to me. While the highest value (1993) is borderline ‘signigicant’ with a p value close to .05, the lowest value (342) is not remotely suspect as it has a p value of 1. I decided to look at the data a bit more closesly and check out some of the higher and lower values of the data.

crime_per_capita[crime_per_capita <500]
[1] 439 342 373 455
crime_per_capita[crime_per_capita >1300]
[1] 1635 1969 1555 1674 1993

The two values at 1900+ seem very high as compared to the rest of the data and the four lowest data points are all at roughly 350 +- 100.

After performing the grubbs test and looking at these data points I would not want to investigate the two 1900+ values further before deciding if they were true outliers or not. It’s possible they are but also could be natural occurences. The low values could be coming from states with less crime and population, say Wyoming, while the two highest could come from areas with a propensity for above average crime rates (e.g. Illinois from Chicago)

Question #2: Change Detection Application

In the insurance world, cusum could be applied to customer claims. These could be done either in claim counts (the number of claims) or claim cost (dollar amount of claims). For something like auto insurance, the cusum could be applied to claim cost per customer per year. The threshold could be determined by profit margin of a customer. Taking the profit made on each customer and subtracting the average claim cost over a 12 year period could be a rule of thumb critical value. This threshold would be a rule of thumb as anytime it was passed would indicate the insurance company is no longer making money on that customer. As for a critical value, this would depend on the company’s goals. If they were very concerned with making money on each customer, they would use a higher critical value (1.5) while if they were less concerned could use a lower one (.5)

Question #3.1: CUSUM for Summer’s End This question focuses on finding when summer ends by way of examining daily temperature highs.

The cusum keeps a running total of deviation from the sample mean. In this case that sample mean is the average temperature during that summer period. As we are trying to find the point at which temperatures are cooling off (i.e. lower than the avg summer temperature from that point onward).

The R package qcc is a statistical control package that has a cusum function within it. Passing each year as the data for the cusum returns a cusum object and plot.

For mu, I considered using the average summer temperature across all years but ultimately decided to use the average summer temperature within a given year. Since the goal was to find the point at which temperatures start to decrease I thought it appropriate to use the average temperature of that summer to determine whether temperatures were decreasing.

I experimented with various threshold values, which within the cusum function are measured in standard errors. I ran various thresholds and ultimately decided on 7 SE to use as the threshold. The default is 5 so this slightly higher threshold would mean a change that registers is more likely to be a true change than a false alarm. I opted to slightly increase the critical value from a default of 1 to 1.2 as this seemed to give better results for indicating a clear change from temperatures increasing or decreasing. With the slightly higher threshold but also slighlty increased sensitivity the results were promising.

The following code runs a loop producing a cusum plot for each year as well as a plot with the last day of summer as indicated by the cusum function: the first day at which a decreasing change is noted.

require(qcc)
Loading required package: qcc
Package 'qcc', version 2.6
Type 'citation("qcc")' for citing this R package in publications.
# Loading the data 
url <- "https://d37djvu3ytnwxt.cloudfront.net/assets/courseware/v1/592f3be3e90d2bdfe6a69f62374a1250/asset-v1:GTx+ISYE6501x+3T2017+type@asset+block/temps.txt"
temps <- read.table(url, header = TRUE)
# Finding the average temperature for each summer to use as the mu 
avg_summer_temp <- c()
for (i in 2:21){
  avg_summer_temp <- append(avg_summer_temp, mean(temps[,i])) 
}
length(avg_summer_temp)
[1] 20
print(avg_summer_temp)
 [1] 83.71545 81.67480 84.26016 83.35772 84.03252 81.55285 83.58537 81.47967 81.76423 83.35772
[11] 83.04878 85.39837 82.51220 80.99187 87.21138 85.27642 84.65041 81.66667 83.94309 83.30081
# The average of the average summer temperatures is 83.33902
avg_avg_summer_temp <- mean(avg_summer_temp)
last_day_of_summer <- c()
for (year in 2:21){
  # Using each year's temps for cusum
  years_cusum <- cusum(temps[,year], 
  # The center is the average of the temperatures. The below value is the average across
  # all years. If it isn't used, the cusum function takes that summer's average temperature
  #center = 83.33902 
  # Decision interval is the threshold for when a change is detected
  
  # Will use 7 
  decision.interval = 7, 
  
  # The critical value (our senstivity to change). Will use 1.2
  se.shift = 1.2,
  
  # Chart name
  data.name = "Summer Temperatures",
  title = "Change Detection in Summer Temperatures with Cusum",
  xlab = "Day of Summer",
  ylab = "Cusum Value")
  
  # Second summer day where decreasing temps have passed decsion threshold
  # Chose the second day to avoid a fluke change detected
  last_day_of_summer <- append(last_day_of_summer, years_cusum$violations$lower[2])
}

years <- seq(from = 1996, to =2015)
plot(years, last_day_of_summer, type = "b", ylim = c(45,100))

To test these results I repeated the cusum function but this time charted the end of summer as the day in which temperatures decreased from then on (i.e. from that point forward each daily temperature was below the mu). I did this with the mu being that summer’s average temperature and also the population mu (avg temperature across all summers).

The results were a bit different in that the cusum version above generally marked the end of summer as later than the true last day of summer. This could be a result of the stringent threshold. The above version also thought the end of the 2013 summer to be very early (~day 50) which was the result of a brief period of unusually cool weather. Overall I think the cusum version did well.

last_day_of_summer <- c()
for (year in 2:21){
  temp_changes <- with(cusum(temps[,year], center = 83.33902, plot = FALSE),
                     cbind(data, "Ci+" = pos, "neg" = -neg))
  # Day of summer 
  day_count <-  1
  
  # vector of days where temperature is NOT increasing
  temp_increase_day <- c()
  
  # Loop to find the last day in which the temperature increases (i.e. daily temp - mu is negative)
  
  # Looping through the cusum data
  for (summer_day in seq(nrow(temp_changes))){
    
    # If the temperature decrease is 0 (i.e. temperature is still increasing)
    # append that day number to our temp_increase_day variable
    if (temp_changes[summer_day,"neg"]==0){
      temp_increase_day <- append(temp_increase_day, day_count)
    }
    # continute on to the next day
    day_count <- day_count + 1
  }
  
  # The day after the last day in which temperature is increasing 
  # Signifies the end of summer (temperatures are now decreasing from this point)
  last_day_of_summer <- append(last_day_of_summer, max(temp_increase_day)+1)
  
}
last_day_of_summer
 [1] 75 84 90 78 67 86 84 68 70 97 75 91 77 59 88 66 92 83 85 74
years <- seq(from = 1996, to =2015)
plot(years, last_day_of_summer, type = "b", ylim = c(45,100), main = "The Last Day of Summer using avg temp across all years")

last_day_of_summer <- c()
for (year in 2:21){
  temp_changes <- with(cusum(temps[,year], plot = FALSE),
                     cbind(data, "Ci+" = pos, "neg" = -neg))
  # Day of summer 
  day_count <-  1
  
  # vector of days where temperature is NOT increasing
  temp_increase_day <- c()
  
  # Loop to find the last day in which the temperature increases (i.e. daily temp - mu is negative)
  
  # Looping through the cusum data
  for (summer_day in seq(nrow(temp_changes))){
    
    # If the temperature decrease is 0 (i.e. temperature is still increasing)
    # append that day number to our temp_increase_day variable
    if (temp_changes[summer_day,"neg"]==0){
      temp_increase_day <- append(temp_increase_day, day_count)
    }
    # continute on to the next day
    day_count <- day_count + 1
  }
  
  # The day after the last day in which temperature is increasing 
  # Signifies the end of summer (temperatures are now decreasing from this point)
  last_day_of_summer <- append(last_day_of_summer, max(temp_increase_day)+1)
  
}
years <- seq(from = 1996, to =2015)
plot(years, last_day_of_summer, type = "b", ylim = c(45,100), main = "The Last Day of Summer")

Question #3.1: CUSUM for Summer’s End To investigate whether Atlanta’s summer climate increased over the years using the cusum method I chose to use the average summer temperature of the first 5 years as mu. If the climate was getting warmer, cusum would detect a postive change earlier and longer.

# First five years of temperatures
five_years <- temps[,2:6]
# 
five_years <- transform(five_years, sum=rowMeans(five_years))
five_year_summer_avg <- mean(five_years[,6]) 
for (year in 2:21){
  # Using each year's temps for cusum
  years_cusum <- cusum(temps[,year], 
  # The center is the average of the temperatures. The below value is the average across
  # all years. If it isn't used, the cusum function takes that summer's average temperature
  center = five_year_summer_avg, 
  
  # Decision interval is the threshold for when a change is detected
  
  # Will use 7
  decision.interval = 7, 
  
  # The critical value (our senstivity to change). Will use 1.2
  se.shift = 1.2,
  
  # Chart name
  data.name = "Summer Temperatures",
  title = "Change Detection in Summer Temperatures with Cusum",
  xlab = "Day of Summer",
  ylab = "Cusum Value")
}

From these charts it is tough to say definitively that the climate is getting warmer. I would lean towards saying yes, particularly because about 7 of the last 10 summers appeared to be very warm. However, 10 is a rather small sample size and a few recent summers like 2013 seemed very mild. A subject like this warrants further investigation. For the sake of answering the question I would say yes the climate is getting warmer.


Ci0tLQp0aXRsZTogIkhXIDMiCm91dHB1dDogaHRtbF9ub3RlYm9vawotLS0KKipRdWVzdGlvbiAjMTogT3V0bGllcnMqKgoKTG9hZGluZyB1cCB0aGUgZGF0YQoKYGBge3J9CnJlcXVpcmUob3V0bGllcnMpCgp1cmwgPC0gImh0dHBzOi8vZDM3ZGp2dTN5dG53eHQuY2xvdWRmcm9udC5uZXQvYXNzZXRzL2NvdXJzZXdhcmUvdjEvMTdiODVjZWE1ZDBlNjEzYmYwODAyNWNhMjkwN2I2MmYvYXNzZXQtdjE6R1R4K0lTWUU2NTAxeCszVDIwMTcrdHlwZUBhc3NldCtibG9jay91c2NyaW1lLnR4dCIKCmRmIDwtIHJlYWQudGFibGUodXJsLCBoZWFkZXIgPSBUUlVFKQpkaW0oZGYpCgojIFNlcGVyYXRpbmcgdGhlIGxhc3QgY29sdW1uIHdlIHdpbGwgZXhhbWluZSBpbnRvIGEgdmFyaWFibGUKY3JpbWVfcGVyX2NhcGl0YSA8LSBkZlssJ0NyaW1lJ10KbGVuZ3RoKGNyaW1lX3Blcl9jYXBpdGEpCmNyaW1lX3Blcl9jYXBpdGEKYGBgClBlcmZyb21pbmcgR3J1YmJzIHRlc3QgZm9yIG91dGxpZXJzCgpUbyBkZXRlcm1pbmUgd2hldGhlciB0aGUgaGlnaGVzdCBhbmQgbG93ZXN0IHZhbHVlcyBhcmUgcG90ZW50aWFsIG91dGxpZXJzLCBJIHVzZWQgdGhlIGdydWJicy50ZXN0KCkgZnVuY3Rpb24gd2l0aCB0eXBlPTEwIHdoaWNoIGxvb2tzIGZvciBvbmUgb3V0bGllci4gVGhlIGZpcnN0IHRlc3QgbG9va3MgYXQgdGhlIGhpZ2hlc3QgdmFsdWUgaW4gdGhlIHNldCBhbmQgdGhlIHNlY29uZCBsb29rcyBmb3IgdGhlIGxvd2VzdCB2YWx1ZSwgaW5kaWNhdGVkIGJ5IHVzaW5nIG9wcG9zaXRlPVRydWUuCmBgYHtyfQojIFRlc3RpbmcgZm9yIHRoZSBoaWdoZXN0IHZhbHVlCmdydWJicy50ZXN0KGNyaW1lX3Blcl9jYXBpdGEsIHR5cGU9MTAsIG9wcG9zaXRlID0gRkFMU0UpCgojIFRlc3RpbmcgZm9yIHRoZSBoaWdoZXN0IHZhbHVlCmdydWJicy50ZXN0KGNyaW1lX3Blcl9jYXBpdGEsIHR5cGU9MTAsIG9wcG9zaXRlID0gVFJVRSkKYGBgClRoZSByZXR1cm5lZCByZXN1bHRzIHNlZW0gYSBiaXQgY3VyaW91cyB0byBtZS4gV2hpbGUgdGhlIGhpZ2hlc3QgdmFsdWUgKDE5OTMpIGlzIGJvcmRlcmxpbmUgJ3NpZ25pZ2ljYW50JyB3aXRoIGEgcCB2YWx1ZSBjbG9zZSB0byAuMDUsIHRoZSBsb3dlc3QgdmFsdWUgKDM0MikgaXMgbm90IHJlbW90ZWx5IHN1c3BlY3QgYXMgaXQgaGFzIGEgcCB2YWx1ZSBvZiAxLiBJIGRlY2lkZWQgdG8gbG9vayBhdCB0aGUgZGF0YSBhIGJpdCBtb3JlIGNsb3Nlc2x5IGFuZCBjaGVjayBvdXQgc29tZSBvZiB0aGUgaGlnaGVyIGFuZCBsb3dlciB2YWx1ZXMgb2YgdGhlIGRhdGEuCmBgYHtyfQpjcmltZV9wZXJfY2FwaXRhW2NyaW1lX3Blcl9jYXBpdGEgPDUwMF0KY3JpbWVfcGVyX2NhcGl0YVtjcmltZV9wZXJfY2FwaXRhID4xMzAwXQpgYGAKVGhlIHR3byB2YWx1ZXMgYXQgMTkwMCsgc2VlbSB2ZXJ5IGhpZ2ggYXMgY29tcGFyZWQgdG8gdGhlIHJlc3Qgb2YgdGhlIGRhdGEgYW5kIHRoZSBmb3VyIGxvd2VzdCBkYXRhIHBvaW50cyBhcmUgYWxsIGF0IHJvdWdobHkgMzUwICstIDEwMC4gCgpBZnRlciBwZXJmb3JtaW5nIHRoZSBncnViYnMgdGVzdCBhbmQgbG9va2luZyBhdCB0aGVzZSBkYXRhIHBvaW50cyBJIHdvdWxkIG5vdCB3YW50IHRvIGludmVzdGlnYXRlIHRoZSB0d28gMTkwMCsgdmFsdWVzIGZ1cnRoZXIgYmVmb3JlIGRlY2lkaW5nIGlmIHRoZXkgd2VyZSB0cnVlIG91dGxpZXJzIG9yIG5vdC4gSXQncyBwb3NzaWJsZSB0aGV5IGFyZSBidXQgYWxzbyBjb3VsZCBiZSBuYXR1cmFsIG9jY3VyZW5jZXMuIFRoZSBsb3cgdmFsdWVzIGNvdWxkIGJlIGNvbWluZyBmcm9tIHN0YXRlcyB3aXRoIGxlc3MgY3JpbWUgYW5kIHBvcHVsYXRpb24sIHNheSBXeW9taW5nLCB3aGlsZSB0aGUgIHR3byBoaWdoZXN0IGNvdWxkIGNvbWUgZnJvbSBhcmVhcyB3aXRoIGEgcHJvcGVuc2l0eSBmb3IgYWJvdmUgYXZlcmFnZSBjcmltZSByYXRlcyAoZS5nLiBJbGxpbm9pcyBmcm9tIENoaWNhZ28pCgoKKipRdWVzdGlvbiAjMjogQ2hhbmdlIERldGVjdGlvbiBBcHBsaWNhdGlvbioqCgpJbiB0aGUgaW5zdXJhbmNlIHdvcmxkLCBjdXN1bSBjb3VsZCBiZSBhcHBsaWVkIHRvIGN1c3RvbWVyIGNsYWltcy4gIFRoZXNlIGNvdWxkIGJlIGRvbmUgZWl0aGVyIGluIGNsYWltIGNvdW50cyAodGhlIG51bWJlciBvZiBjbGFpbXMpIG9yIGNsYWltIGNvc3QgKGRvbGxhciBhbW91bnQgb2YgY2xhaW1zKS4gRm9yIHNvbWV0aGluZyBsaWtlIGF1dG8gaW5zdXJhbmNlLCB0aGUgY3VzdW0gY291bGQgYmUgYXBwbGllZCB0byBjbGFpbSBjb3N0IHBlciBjdXN0b21lciBwZXIgeWVhci4gVGhlIHRocmVzaG9sZCBjb3VsZCBiZSBkZXRlcm1pbmVkIGJ5IHByb2ZpdCBtYXJnaW4gb2YgYSBjdXN0b21lci4gVGFraW5nIHRoZSBwcm9maXQgbWFkZSBvbiBlYWNoIGN1c3RvbWVyIGFuZCBzdWJ0cmFjdGluZyB0aGUgYXZlcmFnZSBjbGFpbSBjb3N0IG92ZXIgYSAxMiB5ZWFyIHBlcmlvZCBjb3VsZCBiZSBhIHJ1bGUgb2YgdGh1bWIgY3JpdGljYWwgdmFsdWUuIFRoaXMgdGhyZXNob2xkIHdvdWxkIGJlIGEgcnVsZSBvZiB0aHVtYiBhcyBhbnl0aW1lIGl0IHdhcyBwYXNzZWQgd291bGQgaW5kaWNhdGUgdGhlIGluc3VyYW5jZSBjb21wYW55IGlzIG5vIGxvbmdlciBtYWtpbmcgbW9uZXkgb24gdGhhdCBjdXN0b21lci4gQXMgZm9yIGEgY3JpdGljYWwgdmFsdWUsIHRoaXMgd291bGQgZGVwZW5kIG9uIHRoZSBjb21wYW55J3MgZ29hbHMuIElmIHRoZXkgd2VyZSB2ZXJ5IGNvbmNlcm5lZCB3aXRoIG1ha2luZyBtb25leSBvbiBlYWNoIGN1c3RvbWVyLCB0aGV5IHdvdWxkIHVzZSBhIGhpZ2hlciBjcml0aWNhbCB2YWx1ZSAoMS41KSB3aGlsZSBpZiB0aGV5IHdlcmUgbGVzcyBjb25jZXJuZWQgY291bGQgdXNlIGEgbG93ZXIgb25lICguNSkKCgoqKlF1ZXN0aW9uICMzLjE6IENVU1VNIGZvciBTdW1tZXIncyBFbmQqKgpUaGlzIHF1ZXN0aW9uIGZvY3VzZXMgb24gZmluZGluZyB3aGVuIHN1bW1lciBlbmRzIGJ5IHdheSBvZiBleGFtaW5pbmcgZGFpbHkgdGVtcGVyYXR1cmUgaGlnaHMuIAoKVGhlIGN1c3VtIGtlZXBzIGEgcnVubmluZyB0b3RhbCBvZiBkZXZpYXRpb24gZnJvbSB0aGUgc2FtcGxlIG1lYW4uIEluIHRoaXMgY2FzZSB0aGF0IHNhbXBsZSBtZWFuIGlzIHRoZSBhdmVyYWdlIHRlbXBlcmF0dXJlIGR1cmluZyB0aGF0IHN1bW1lciBwZXJpb2QuIEFzIHdlIGFyZSB0cnlpbmcgdG8gZmluZCB0aGUgcG9pbnQgYXQgd2hpY2ggdGVtcGVyYXR1cmVzIGFyZSBjb29saW5nIG9mZiAoaS5lLiBsb3dlciB0aGFuIHRoZSBhdmcgc3VtbWVyIHRlbXBlcmF0dXJlIGZyb20gdGhhdCBwb2ludCBvbndhcmQpLiAKClRoZSBSIHBhY2thZ2UgcWNjIGlzIGEgc3RhdGlzdGljYWwgY29udHJvbCBwYWNrYWdlIHRoYXQgaGFzIGEgY3VzdW0gZnVuY3Rpb24gd2l0aGluIGl0LiBQYXNzaW5nIGVhY2ggeWVhciBhcyB0aGUgZGF0YSBmb3IgdGhlIGN1c3VtIHJldHVybnMgYSBjdXN1bSBvYmplY3QgYW5kIHBsb3QuCgpGb3IgbXUsIEkgY29uc2lkZXJlZCB1c2luZyB0aGUgYXZlcmFnZSBzdW1tZXIgdGVtcGVyYXR1cmUgYWNyb3NzIGFsbCB5ZWFycyBidXQgdWx0aW1hdGVseSBkZWNpZGVkIHRvIHVzZSB0aGUgYXZlcmFnZSBzdW1tZXIgdGVtcGVyYXR1cmUgd2l0aGluIGEgZ2l2ZW4geWVhci4gU2luY2UgdGhlIGdvYWwgd2FzIHRvIGZpbmQgdGhlIHBvaW50IGF0IHdoaWNoIHRlbXBlcmF0dXJlcyBzdGFydCB0byBkZWNyZWFzZSBJIHRob3VnaHQgaXQgYXBwcm9wcmlhdGUgdG8gdXNlIHRoZSBhdmVyYWdlIHRlbXBlcmF0dXJlIG9mIHRoYXQgc3VtbWVyIHRvIGRldGVybWluZSB3aGV0aGVyIHRlbXBlcmF0dXJlcyB3ZXJlIGRlY3JlYXNpbmcuIAoKSSBleHBlcmltZW50ZWQgd2l0aCB2YXJpb3VzIHRocmVzaG9sZCB2YWx1ZXMsIHdoaWNoIHdpdGhpbiB0aGUgY3VzdW0gZnVuY3Rpb24gYXJlIG1lYXN1cmVkIGluIHN0YW5kYXJkIGVycm9ycy4gSSByYW4gdmFyaW91cyB0aHJlc2hvbGRzIGFuZCB1bHRpbWF0ZWx5IGRlY2lkZWQgb24gNyBTRSB0byB1c2UgYXMgdGhlIHRocmVzaG9sZC4gVGhlIGRlZmF1bHQgaXMgNSBzbyB0aGlzIHNsaWdodGx5IGhpZ2hlciB0aHJlc2hvbGQgd291bGQgbWVhbiBhIGNoYW5nZSB0aGF0IHJlZ2lzdGVycyBpcyBtb3JlIGxpa2VseSB0byBiZSBhIHRydWUgY2hhbmdlIHRoYW4gYSBmYWxzZSBhbGFybS4gSSBvcHRlZCB0byBzbGlnaHRseSBpbmNyZWFzZSB0aGUgY3JpdGljYWwgdmFsdWUgZnJvbSBhIGRlZmF1bHQgb2YgMSB0byAxLjIgYXMgdGhpcyBzZWVtZWQgdG8gZ2l2ZSBiZXR0ZXIgcmVzdWx0cyBmb3IgaW5kaWNhdGluZyBhIGNsZWFyIGNoYW5nZSBmcm9tIHRlbXBlcmF0dXJlcyBpbmNyZWFzaW5nIG9yIGRlY3JlYXNpbmcuIFdpdGggdGhlIHNsaWdodGx5IGhpZ2hlciB0aHJlc2hvbGQgYnV0IGFsc28gc2xpZ2hsdHkgaW5jcmVhc2VkIHNlbnNpdGl2aXR5IHRoZSByZXN1bHRzIHdlcmUgcHJvbWlzaW5nLiAKClRoZSBmb2xsb3dpbmcgY29kZSBydW5zIGEgbG9vcCBwcm9kdWNpbmcgYSBjdXN1bSBwbG90IGZvciBlYWNoIHllYXIgYXMgd2VsbCBhcyBhIHBsb3Qgd2l0aCB0aGUgbGFzdCBkYXkgb2Ygc3VtbWVyIGFzIGluZGljYXRlZCBieSB0aGUgY3VzdW0gZnVuY3Rpb246IHRoZSBmaXJzdCBkYXkgYXQgd2hpY2ggYSBkZWNyZWFzaW5nIGNoYW5nZSBpcyBub3RlZC4gCgpgYGB7cn0KcmVxdWlyZShxY2MpCgojIExvYWRpbmcgdGhlIGRhdGEgCnVybCA8LSAiaHR0cHM6Ly9kMzdkanZ1M3l0bnd4dC5jbG91ZGZyb250Lm5ldC9hc3NldHMvY291cnNld2FyZS92MS81OTJmM2JlM2U5MGQyYmRmZTZhNjlmNjIzNzRhMTI1MC9hc3NldC12MTpHVHgrSVNZRTY1MDF4KzNUMjAxNyt0eXBlQGFzc2V0K2Jsb2NrL3RlbXBzLnR4dCIKCnRlbXBzIDwtIHJlYWQudGFibGUodXJsLCBoZWFkZXIgPSBUUlVFKQoKIyBGaW5kaW5nIHRoZSBhdmVyYWdlIHRlbXBlcmF0dXJlIGZvciBlYWNoIHN1bW1lciB0byB1c2UgYXMgdGhlIG11IAphdmdfc3VtbWVyX3RlbXAgPC0gYygpCmZvciAoaSBpbiAyOjIxKXsKICBhdmdfc3VtbWVyX3RlbXAgPC0gYXBwZW5kKGF2Z19zdW1tZXJfdGVtcCwgbWVhbih0ZW1wc1ssaV0pKSAKfQpsZW5ndGgoYXZnX3N1bW1lcl90ZW1wKQpwcmludChhdmdfc3VtbWVyX3RlbXApCgojIFRoZSBhdmVyYWdlIG9mIHRoZSBhdmVyYWdlIHN1bW1lciB0ZW1wZXJhdHVyZXMgaXMgODMuMzM5MDIKYXZnX2F2Z19zdW1tZXJfdGVtcCA8LSBtZWFuKGF2Z19zdW1tZXJfdGVtcCkKCmxhc3RfZGF5X29mX3N1bW1lciA8LSBjKCkKCmZvciAoeWVhciBpbiAyOjIxKXsKICAjIFVzaW5nIGVhY2ggeWVhcidzIHRlbXBzIGZvciBjdXN1bQogIHllYXJzX2N1c3VtIDwtIGN1c3VtKHRlbXBzWyx5ZWFyXSwgCiAgIyBUaGUgY2VudGVyIGlzIHRoZSBhdmVyYWdlIG9mIHRoZSB0ZW1wZXJhdHVyZXMuIFRoZSBiZWxvdyB2YWx1ZSBpcyB0aGUgYXZlcmFnZSBhY3Jvc3MKICAjIGFsbCB5ZWFycy4gSWYgaXQgaXNuJ3QgdXNlZCwgdGhlIGN1c3VtIGZ1bmN0aW9uIHRha2VzIHRoYXQgc3VtbWVyJ3MgYXZlcmFnZSB0ZW1wZXJhdHVyZQogICNjZW50ZXIgPSA4My4zMzkwMiAKICAjIERlY2lzaW9uIGludGVydmFsIGlzIHRoZSB0aHJlc2hvbGQgZm9yIHdoZW4gYSBjaGFuZ2UgaXMgZGV0ZWN0ZWQKICAKICAjIFdpbGwgdXNlIDcgCiAgZGVjaXNpb24uaW50ZXJ2YWwgPSA3LCAKICAKICAjIFRoZSBjcml0aWNhbCB2YWx1ZSAob3VyIHNlbnN0aXZpdHkgdG8gY2hhbmdlKS4gV2lsbCB1c2UgMS4yCiAgc2Uuc2hpZnQgPSAxLjIsCiAgCiAgIyBDaGFydCBuYW1lCiAgZGF0YS5uYW1lID0gIlN1bW1lciBUZW1wZXJhdHVyZXMiLAogIHRpdGxlCT0gIkNoYW5nZSBEZXRlY3Rpb24gaW4gU3VtbWVyIFRlbXBlcmF0dXJlcyB3aXRoIEN1c3VtIiwKICB4bGFiID0gIkRheSBvZiBTdW1tZXIiLAogIHlsYWIgPSAiQ3VzdW0gVmFsdWUiKQogIAogICMgU2Vjb25kIHN1bW1lciBkYXkgd2hlcmUgZGVjcmVhc2luZyB0ZW1wcyBoYXZlIHBhc3NlZCBkZWNzaW9uIHRocmVzaG9sZAogICMgQ2hvc2UgdGhlIHNlY29uZCBkYXkgdG8gYXZvaWQgYSBmbHVrZSBjaGFuZ2UgZGV0ZWN0ZWQKICBsYXN0X2RheV9vZl9zdW1tZXIgPC0gYXBwZW5kKGxhc3RfZGF5X29mX3N1bW1lciwgeWVhcnNfY3VzdW0kdmlvbGF0aW9ucyRsb3dlclsyXSkKfQp5ZWFycyA8LSBzZXEoZnJvbSA9IDE5OTYsIHRvID0yMDE1KQoKcGxvdCh5ZWFycywgbGFzdF9kYXlfb2Zfc3VtbWVyLCB0eXBlID0gImIiLCB5bGltID0gYyg0NSwxMDApKQpgYGAKVG8gdGVzdCB0aGVzZSByZXN1bHRzIEkgcmVwZWF0ZWQgdGhlIGN1c3VtIGZ1bmN0aW9uIGJ1dCB0aGlzIHRpbWUgY2hhcnRlZCB0aGUgZW5kIG9mIHN1bW1lciBhcyB0aGUgZGF5IGluIHdoaWNoIHRlbXBlcmF0dXJlcyBkZWNyZWFzZWQgZnJvbSB0aGVuIG9uIChpLmUuIGZyb20gdGhhdCBwb2ludCBmb3J3YXJkIGVhY2ggZGFpbHkgdGVtcGVyYXR1cmUgd2FzIGJlbG93IHRoZSBtdSkuIEkgZGlkIHRoaXMgd2l0aCB0aGUgbXUgYmVpbmcgdGhhdCBzdW1tZXIncyBhdmVyYWdlIHRlbXBlcmF0dXJlIGFuZCBhbHNvIHRoZSBwb3B1bGF0aW9uIG11IChhdmcgdGVtcGVyYXR1cmUgYWNyb3NzIGFsbCBzdW1tZXJzKS4gCgpUaGUgcmVzdWx0cyB3ZXJlIGEgYml0IGRpZmZlcmVudCBpbiB0aGF0IHRoZSBjdXN1bSB2ZXJzaW9uIGFib3ZlIGdlbmVyYWxseSBtYXJrZWQgdGhlIGVuZCBvZiBzdW1tZXIgYXMgbGF0ZXIgdGhhbiB0aGUgdHJ1ZSBsYXN0IGRheSBvZiBzdW1tZXIuIFRoaXMgY291bGQgYmUgYSByZXN1bHQgb2YgdGhlIHN0cmluZ2VudCB0aHJlc2hvbGQuIFRoZSBhYm92ZSB2ZXJzaW9uIGFsc28gdGhvdWdodCB0aGUgZW5kIG9mIHRoZSAyMDEzIHN1bW1lciB0byBiZSB2ZXJ5IGVhcmx5ICh+ZGF5IDUwKSB3aGljaCB3YXMgdGhlIHJlc3VsdCBvZiBhIGJyaWVmIHBlcmlvZCBvZiB1bnVzdWFsbHkgY29vbCB3ZWF0aGVyLiBPdmVyYWxsIEkgdGhpbmsgdGhlIGN1c3VtIHZlcnNpb24gZGlkIHdlbGwuICAKYGBge3J9CgpsYXN0X2RheV9vZl9zdW1tZXIgPC0gYygpCmZvciAoeWVhciBpbiAyOjIxKXsKICB0ZW1wX2NoYW5nZXMgPC0gd2l0aChjdXN1bSh0ZW1wc1sseWVhcl0sIGNlbnRlciA9IDgzLjMzOTAyLCBwbG90ID0gRkFMU0UpLAogICAgICAgICAgICAgICAgICAgICBjYmluZChkYXRhLCAiQ2krIiA9IHBvcywgIm5lZyIgPSAtbmVnKSkKICAjIERheSBvZiBzdW1tZXIgCiAgZGF5X2NvdW50IDwtICAxCiAgCiAgIyB2ZWN0b3Igb2YgZGF5cyB3aGVyZSB0ZW1wZXJhdHVyZSBpcyBOT1QgaW5jcmVhc2luZwogIHRlbXBfaW5jcmVhc2VfZGF5IDwtIGMoKQogIAogICMgTG9vcCB0byBmaW5kIHRoZSBsYXN0IGRheSBpbiB3aGljaCB0aGUgdGVtcGVyYXR1cmUgaW5jcmVhc2VzIChpLmUuIGRhaWx5IHRlbXAgLSBtdSBpcyBuZWdhdGl2ZSkKICAKICAjIExvb3BpbmcgdGhyb3VnaCB0aGUgY3VzdW0gZGF0YQogIGZvciAoc3VtbWVyX2RheSBpbiBzZXEobnJvdyh0ZW1wX2NoYW5nZXMpKSl7CiAgICAKICAgICMgSWYgdGhlIHRlbXBlcmF0dXJlIGRlY3JlYXNlIGlzIDAgKGkuZS4gdGVtcGVyYXR1cmUgaXMgc3RpbGwgaW5jcmVhc2luZykKICAgICMgYXBwZW5kIHRoYXQgZGF5IG51bWJlciB0byBvdXIgdGVtcF9pbmNyZWFzZV9kYXkgdmFyaWFibGUKICAgIGlmICh0ZW1wX2NoYW5nZXNbc3VtbWVyX2RheSwibmVnIl09PTApewogICAgICB0ZW1wX2luY3JlYXNlX2RheSA8LSBhcHBlbmQodGVtcF9pbmNyZWFzZV9kYXksIGRheV9jb3VudCkKICAgIH0KICAgICMgY29udGludXRlIG9uIHRvIHRoZSBuZXh0IGRheQogICAgZGF5X2NvdW50IDwtIGRheV9jb3VudCArIDEKICB9CiAgCiAgIyBUaGUgZGF5IGFmdGVyIHRoZSBsYXN0IGRheSBpbiB3aGljaCB0ZW1wZXJhdHVyZSBpcyBpbmNyZWFzaW5nIAogICMgU2lnbmlmaWVzIHRoZSBlbmQgb2Ygc3VtbWVyICh0ZW1wZXJhdHVyZXMgYXJlIG5vdyBkZWNyZWFzaW5nIGZyb20gdGhpcyBwb2ludCkKICBsYXN0X2RheV9vZl9zdW1tZXIgPC0gYXBwZW5kKGxhc3RfZGF5X29mX3N1bW1lciwgbWF4KHRlbXBfaW5jcmVhc2VfZGF5KSsxKQogIAp9CgpsYXN0X2RheV9vZl9zdW1tZXIKeWVhcnMgPC0gc2VxKGZyb20gPSAxOTk2LCB0byA9MjAxNSkKCnBsb3QoeWVhcnMsIGxhc3RfZGF5X29mX3N1bW1lciwgdHlwZSA9ICJiIiwgeWxpbSA9IGMoNDUsMTAwKSwgbWFpbiA9ICJUaGUgTGFzdCBEYXkgb2YgU3VtbWVyIHVzaW5nIGF2ZyB0ZW1wIGFjcm9zcyBhbGwgeWVhcnMiKQoKbGFzdF9kYXlfb2Zfc3VtbWVyIDwtIGMoKQpmb3IgKHllYXIgaW4gMjoyMSl7CiAgdGVtcF9jaGFuZ2VzIDwtIHdpdGgoY3VzdW0odGVtcHNbLHllYXJdLCBwbG90ID0gRkFMU0UpLAogICAgICAgICAgICAgICAgICAgICBjYmluZChkYXRhLCAiQ2krIiA9IHBvcywgIm5lZyIgPSAtbmVnKSkKICAjIERheSBvZiBzdW1tZXIgCiAgZGF5X2NvdW50IDwtICAxCiAgCiAgIyB2ZWN0b3Igb2YgZGF5cyB3aGVyZSB0ZW1wZXJhdHVyZSBpcyBOT1QgaW5jcmVhc2luZwogIHRlbXBfaW5jcmVhc2VfZGF5IDwtIGMoKQogIAogICMgTG9vcCB0byBmaW5kIHRoZSBsYXN0IGRheSBpbiB3aGljaCB0aGUgdGVtcGVyYXR1cmUgaW5jcmVhc2VzIChpLmUuIGRhaWx5IHRlbXAgLSBtdSBpcyBuZWdhdGl2ZSkKICAKICAjIExvb3BpbmcgdGhyb3VnaCB0aGUgY3VzdW0gZGF0YQogIGZvciAoc3VtbWVyX2RheSBpbiBzZXEobnJvdyh0ZW1wX2NoYW5nZXMpKSl7CiAgICAKICAgICMgSWYgdGhlIHRlbXBlcmF0dXJlIGRlY3JlYXNlIGlzIDAgKGkuZS4gdGVtcGVyYXR1cmUgaXMgc3RpbGwgaW5jcmVhc2luZykKICAgICMgYXBwZW5kIHRoYXQgZGF5IG51bWJlciB0byBvdXIgdGVtcF9pbmNyZWFzZV9kYXkgdmFyaWFibGUKICAgIGlmICh0ZW1wX2NoYW5nZXNbc3VtbWVyX2RheSwibmVnIl09PTApewogICAgICB0ZW1wX2luY3JlYXNlX2RheSA8LSBhcHBlbmQodGVtcF9pbmNyZWFzZV9kYXksIGRheV9jb3VudCkKICAgIH0KICAgICMgY29udGludXRlIG9uIHRvIHRoZSBuZXh0IGRheQogICAgZGF5X2NvdW50IDwtIGRheV9jb3VudCArIDEKICB9CiAgCiAgIyBUaGUgZGF5IGFmdGVyIHRoZSBsYXN0IGRheSBpbiB3aGljaCB0ZW1wZXJhdHVyZSBpcyBpbmNyZWFzaW5nIAogICMgU2lnbmlmaWVzIHRoZSBlbmQgb2Ygc3VtbWVyICh0ZW1wZXJhdHVyZXMgYXJlIG5vdyBkZWNyZWFzaW5nIGZyb20gdGhpcyBwb2ludCkKICBsYXN0X2RheV9vZl9zdW1tZXIgPC0gYXBwZW5kKGxhc3RfZGF5X29mX3N1bW1lciwgbWF4KHRlbXBfaW5jcmVhc2VfZGF5KSsxKQogIAp9Cgp5ZWFycyA8LSBzZXEoZnJvbSA9IDE5OTYsIHRvID0yMDE1KQoKcGxvdCh5ZWFycywgbGFzdF9kYXlfb2Zfc3VtbWVyLCB0eXBlID0gImIiLCB5bGltID0gYyg0NSwxMDApLCBtYWluID0gIlRoZSBMYXN0IERheSBvZiBTdW1tZXIiKQpgYGAKKipRdWVzdGlvbiAjMy4xOiBDVVNVTSBmb3IgU3VtbWVyJ3MgRW5kKioKVG8gaW52ZXN0aWdhdGUgd2hldGhlciBBdGxhbnRhJ3Mgc3VtbWVyIGNsaW1hdGUgaW5jcmVhc2VkIG92ZXIgdGhlIHllYXJzIHVzaW5nIHRoZSBjdXN1bSBtZXRob2QgSSBjaG9zZSB0byB1c2UgdGhlIGF2ZXJhZ2Ugc3VtbWVyIHRlbXBlcmF0dXJlIG9mIHRoZSBmaXJzdCA1IHllYXJzIGFzIG11LiBJZiB0aGUgY2xpbWF0ZSB3YXMgZ2V0dGluZyB3YXJtZXIsIGN1c3VtIHdvdWxkIGRldGVjdCBhIHBvc3RpdmUgY2hhbmdlIGVhcmxpZXIgYW5kIGxvbmdlci4KCgpgYGB7cn0KIyBGaXJzdCBmaXZlIHllYXJzIG9mIHRlbXBlcmF0dXJlcwpmaXZlX3llYXJzIDwtIHRlbXBzWywyOjZdCgojIApmaXZlX3llYXJzIDwtIHRyYW5zZm9ybShmaXZlX3llYXJzLCBzdW09cm93TWVhbnMoZml2ZV95ZWFycykpCgoKZml2ZV95ZWFyX3N1bW1lcl9hdmcgPC0gbWVhbihmaXZlX3llYXJzWyw2XSkgCgpmb3IgKHllYXIgaW4gMjoyMSl7CiAgIyBVc2luZyBlYWNoIHllYXIncyB0ZW1wcyBmb3IgY3VzdW0KICB5ZWFyc19jdXN1bSA8LSBjdXN1bSh0ZW1wc1sseWVhcl0sIAogICMgVGhlIGNlbnRlciBpcyB0aGUgYXZlcmFnZSBvZiB0aGUgdGVtcGVyYXR1cmVzLiBUaGUgYmVsb3cgdmFsdWUgaXMgdGhlIGF2ZXJhZ2UgYWNyb3NzCiAgIyBhbGwgeWVhcnMuIElmIGl0IGlzbid0IHVzZWQsIHRoZSBjdXN1bSBmdW5jdGlvbiB0YWtlcyB0aGF0IHN1bW1lcidzIGF2ZXJhZ2UgdGVtcGVyYXR1cmUKICBjZW50ZXIgPSBmaXZlX3llYXJfc3VtbWVyX2F2ZywgCiAgCiAgIyBEZWNpc2lvbiBpbnRlcnZhbCBpcyB0aGUgdGhyZXNob2xkIGZvciB3aGVuIGEgY2hhbmdlIGlzIGRldGVjdGVkCiAgCiAgIyBXaWxsIHVzZSA3CiAgZGVjaXNpb24uaW50ZXJ2YWwgPSA3LCAKICAKICAjIFRoZSBjcml0aWNhbCB2YWx1ZSAob3VyIHNlbnN0aXZpdHkgdG8gY2hhbmdlKS4gV2lsbCB1c2UgMS4yCiAgc2Uuc2hpZnQgPSAxLjIsCiAgCiAgIyBDaGFydCBuYW1lCiAgZGF0YS5uYW1lID0gIlN1bW1lciBUZW1wZXJhdHVyZXMiLAogIHRpdGxlCT0gIkNoYW5nZSBEZXRlY3Rpb24gaW4gU3VtbWVyIFRlbXBlcmF0dXJlcyB3aXRoIEN1c3VtIiwKICB4bGFiID0gIkRheSBvZiBTdW1tZXIiLAogIHlsYWIgPSAiQ3VzdW0gVmFsdWUiKQp9CgpgYGAKRnJvbSB0aGVzZSBjaGFydHMgaXQgaXMgdG91Z2ggdG8gc2F5IGRlZmluaXRpdmVseSB0aGF0IHRoZSBjbGltYXRlIGlzIGdldHRpbmcgd2FybWVyLiBJIHdvdWxkIGxlYW4gdG93YXJkcyBzYXlpbmcgeWVzLCBwYXJ0aWN1bGFybHkgYmVjYXVzZSBhYm91dCA3IG9mIHRoZSBsYXN0IDEwIHN1bW1lcnMgYXBwZWFyZWQgdG8gYmUgdmVyeSB3YXJtLiBIb3dldmVyLCAxMCBpcyBhIHJhdGhlciBzbWFsbCBzYW1wbGUgc2l6ZSBhbmQgYSBmZXcgcmVjZW50IHN1bW1lcnMgbGlrZSAyMDEzIHNlZW1lZCB2ZXJ5IG1pbGQuIEEgc3ViamVjdCBsaWtlIHRoaXMgd2FycmFudHMgZnVydGhlciBpbnZlc3RpZ2F0aW9uLiBGb3IgdGhlIHNha2Ugb2YgYW5zd2VyaW5nIHRoZSBxdWVzdGlvbiBJIHdvdWxkIHNheSB5ZXMgdGhlIGNsaW1hdGUgaXMgZ2V0dGluZyB3YXJtZXIuCmBgYAoKCmBgYAoK